计数是通过逻辑结构确定有限集合大小的艺术,无需繁琐的逐项统计。借助这一方法,我们可以解决从简单的菜单组合到复杂的密码学排列等各种问题。
"或"与"与"的逻辑
两个基本原理支撑着整个组合数学领域。其应用完全取决于我们是否将任务视为从多个类别中进行单一选择,还是作为一系列连续的选择过程。
加法原理(求和法则)
如果集合 $X$ 被划分为互不相交的子集 $X_1, X_2, \dots, X_n$,那么集合 $X$ 中元素总数 $|X|$ 等于这些子集大小之和:
$$|X| = |X_1| + |X_2| + \dots + |X_n|$$
类比: 在凯的快餐店点餐时,你可以从主菜菜单中选一个三明治,或者从开胃菜菜单中选一份开胃菜。你只能二选一,不能同时要两者。
乘法原理(乘积法则)
如果一项活动包含 $t$ 个连续步骤,第 $i$ 步有 $n_i$ 种可能结果,则完成该任务的总方式数为各步可能性的乘积:
$$N = n_1 \times n_2 \times \dots \times n_t$$
类比: 配置一辆“大皮卡”卡车。你必须选择一种发动机(5种选项)和一种驾驶室样式(3种选项)。总共有 $5 \times 3 = 15$ 种配置方式。
代码实现与复杂度
在计算机科学中,这些原理体现在循环结构中。顺序循环体现加法原理,嵌套循环则体现乘法原理。
// 加法原理(执行次数:m + n)
for i = 1 to m: println(i)
for j = 1 to n: println(j)
// 乘法原理(执行次数:m × n)
for i = 1 to m:
for j = 1 to n:
println(i, j)
for i = 1 to m: println(i)
for j = 1 to n: println(j)
// 乘法原理(执行次数:m × n)
for i = 1 to m:
for j = 1 to n:
println(i, j)
🎯 核心原则
根据关键词区分:'或'表示加法(互斥选择),而'与'或'连续'表示乘法(序列中的独立步骤)。